﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
//复杂度分析
//时间复杂度：建堆O（n），调整排序O(nlogn)
//空间复杂度：建堆O（1）
//稳定性：不稳定



//堆是由顺序表组成的，是二叉树，但是不是链表
class solHeap
{
    public void swap(ref int x, ref int y)
    {
        int temp=x; x=y; y=temp;

    }
    public void swap(int[] nums, int x, int y)
    {
        int temp = nums[x];
        nums[x] = nums[y];
        nums[y] = temp;
       

    }
    public void makeBigHeap(int[] nums,int len)
    { 
       

        for (int i = len/2;i>=0; i--) { //只遍历一半，也就是所有的分支节点

            adjustHeap(nums,i,len);
            
        }

    }
    public void adjustHeap(int[] nums, int i, int len)
    {
        int left = 2 * i + 1;//也有可能没有孩子

        int right = 2 * i + 2;
        int largest = i;
        if (left < len && nums[largest] < nums[left])
        {

            largest = left;//larger变化了一次才有意义

        }

        if (right < len && nums[largest] < nums[right])
        {

            largest = right;


        }

        if (largest != i)//只有调整过才执行，不然无限循环了
        {
            //swap(ref nums[i], ref nums[larger]);
            swap(nums, i, largest);
         adjustHeap(nums, largest, len);//larger变化了一次才有意义
        }


    }
    public void adjustHeap2(int[] nums,int i,int len)
    {
        int left = 2 * i + 1;//也有可能没有孩子

        int right = 2 * i + 2;
        int larger = i;
        if (left < len&& nums[i] < nums[left])
        {

            larger=left;
         
        }

        if (right < len && nums[i] < nums[right])
        {
            
            larger = right;
                
            
        }

        if (larger!=i)//只有调整过才执行，不然无限循环了
        {
            //swap(ref nums[i], ref nums[larger]);
            swap(nums,i,larger);


            adjustHeap(nums, i, len);//调整新生成的（新的堆，小元素下坠）  ，,
            //这个语句看着不正确的原因是，这次交换实际上只把孩子里面较大的交换了一次，导致有一个孩子还是比父亲大nums[i] < nums[right]不是i和righrt比，而是larger和right比
            //还要进行第二次循环


            //adjustHeap(nums, larger, len);//,这个是错的
        }


    }


}
class ProgramHaep
{

    static void MainHaep(string[] args)
    {

        //int[] nums = { 53, 17, 78, 09, 45, 65, 87, 32 };
        int[] nums = { 3, 2, 1, 5, 6, 4};
        solHeap solHeap = new solHeap();
        int len = nums.Length;
        //先构建一个大根堆
        solHeap.makeBigHeap(nums,len);//这个大根堆只有最上面的最大


        for (int i = nums.Length - 1; i >= 0; i--)
        {
            solHeap.swap(ref nums[i], ref nums[0]);
            //交换之后调整一下就行，不用重构
            len--;
            //solHeap.adjustHeap(nums, 0, len);//只需要调整一侧
            solHeap.makeBigHeap(nums, len);//结果一样，但是时间不一样，调整比构建快

        }
        


        for (int i = 0; i < nums.Length; i++)
        {
            Console.WriteLine(nums[i]);
        }
        Console.ReadKey();





    }
}
